import java.util.Arrays;

/**
 * 手动实现 “堆排序”：是选择排序的改进版
 *      （1）若要升序排序：选择大顶堆方式
 *      （2）若要降序排序，选择小顶堆方式
 */
public class HeapSortDemo {
    //定义一个中转变量
    public static int temp;

    public static void main(String[] args) {
        // 数组升序排序
        int[] arr = {4,5,1,6,2,7,3,8};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //堆排序算法：大顶堆方式
    public static void heapSort(int[] arr){
        //1.循环构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //注意：arr.length/2-1 ：这个公式是计算完全二叉树中，最后一个“非叶子节点索引”的公式，
            // 这个公式的值依次减一，就依次表示前一个非叶子节点的索引，直到0为止（即，到根节点为止）
            adjustHeap(arr,i, arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            //总共交换arr.length - 1次，每次都是堆顶与末尾节点交换
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //每交换完依次堆顶，就要重新构造一次大顶堆，且长度要依次递减
            //非叶子节点直接从根节点0，开始就ok，因为首尾交换只会改变根节点的结构，其他地方还是大顶堆结构
            adjustHeap(arr,0, i);
        }
    }

    /**
     * 将无序数组(对应的二叉树) 调整成一个大顶堆
     *           完成将以 i 对应的非叶子节点的树 调整大顶堆   {4,6,8,5,9} => i=1时 {4,9,8,5,6}
     *           第二次 传入的是 i = 0 =>  {9,6,8,5,4}
     * @param arr:需要排序的数组
     * @param i：非叶子节点的数组下标
     * @param length：原数组的长度
     */
    public static void adjustHeap(int[] arr,int i,int length){
        //获取非叶子节点的值
        int temp = arr[i];
        //根据非叶子节点的子节点来进行判断
        for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
            //比较两个子节点的大小，然后将指针指向较大的那个节点
            if (j + 1 < length && arr[j] < arr[j+1]) {
                //若当前非叶子节点的左节点小于右节点，则将j指向右节点
                j++;
            }
            if (arr[j] > temp) {
                //若子节点大于父节点，则将子节点值，赋给父节点
                arr[i] = arr[j];
                //再将非叶子节点的指针i，指向j，即指向当前节点，继续循环比较
                i = j;
            }else {
                //若子节点小于等于父节点，则直接结束当前循环，这种情况下，不可能还有子节点需要比较
                break;
            }
        }
        //for循环结束后 将 以 i 为父节点的树 的最大值 放到了最顶上(局部)
        arr[i] = temp;// 将temp放在调整后的位置
    }
}
